package LEETCODE2023.BISHUA100;

import java.util.*;

public class SolutionL103锯齿形层序遍历双端队列 {
    public static void main(String[] args) {

    }

    //使用栈解
    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        boolean tag = true;
        while (!stack.isEmpty()) {
            ArrayList<Integer> temp = new ArrayList<>();
            int n = stack.size();
            Queue<TreeNode> lib = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                lib.offer(stack.pop());
            }
            for (int i = 0; i < n; i++) {
                TreeNode node = lib.poll();
                temp.add(node.val);
                if (tag) {
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                } else {
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                }
            }
            ans.add(temp);
            tag = !tag;
        }
        return ans;
    }
    //错误做法
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean tag = true;
        while (!queue.isEmpty()) {
            ArrayList<Integer> temp = new ArrayList<>();
            int n = queue.size();
            Queue<TreeNode> lib = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                lib.offer(queue.poll());
            }
            for (int i = 0; i < n; i++) {
                TreeNode node = lib.poll();
                temp.add(node.val);
                if (tag) {
                    if (node.left != null) {
                        queue.offerFirst(node.left);
                    }
                    if (node.right != null) {
                        queue.offerFirst(node.right);
                    }
                } else {
                    if (node.right != null) {
                        queue.offerFirst(node.right);
                    }
                    if (node.left != null) {
                        queue.offerFirst(node.left);
                    }
                }
            }
            ans.add(temp);
            tag = !tag;
        }
        return ans;
    }
}
